package main

/**
 * 线段树方法
 */
type MyCalendar struct {
	stTree *SegmentTree
}

func Constructor() MyCalendar {
	return MyCalendar{&SegmentTree{&Node{nil, nil, 0, 1e9, false, false}}}
}

func (this *MyCalendar) Book(start int, end int) bool {
	res := this.stTree.Query(start, end, this.stTree.root)
	if res {
		return false
	}
	this.stTree.Update(start, end, true, this.stTree.root)
	return true
}

type Node struct {
	left, right *Node
	start, end  int
	val         bool
	lazy        bool
}

type SegmentTree struct {
	root *Node
}

func (this *SegmentTree) Update(start int, end int, val bool, node *Node) {
	if start > end {
		return
	}
	// 当起终点范围包含node节点范围时
	if start <= node.start && node.end <= end {
		node.val = val
		node.lazy = true
		return
	}
	// 动态开点下传lazy
	this.Pushdown(node)
	mid := (node.start + node.end) >> 1
	if start <= mid {
		this.Update(start, end, val, node.left)
	}
	if end > mid {
		this.Update(start, end, val, node.right)
	}
	this.Pushup(node)
}

func (this *SegmentTree) Pushdown(node *Node) {
	mid := (node.start + node.end) >> 1
	if node.left == nil {
		node.left = &Node{nil, nil, node.start, mid, false, false}
	}
	if node.right == nil {
		node.right = &Node{nil, nil, mid + 1, node.end, false, false}
	}
	if node.lazy {
		node.left.lazy = true
		node.right.lazy = true
		node.lazy = false
		node.left.val = node.val
		node.right.val = node.val
	}
}

func (this *SegmentTree) Pushup(node *Node) {
	node.val = node.left.val || node.right.val
}

func (this *SegmentTree) Query(start int, end int, node *Node) bool {
	if start > end {
		return false
	}
	if start <= node.start && node.end <= end {
		return node.val
	}
	this.Pushdown(node)
	mid := (node.start + node.end) >> 1
	ans := false
	if start <= mid {
		ans = ans || this.Query(start, end, node.left)
	}
	if end > mid {
		ans = ans || this.Query(start, end, node.right)
	}
	return ans

}

/**
 * Your MyCalendar object will be instantiated and called as such:
 * obj := Constructor();
 * param_1 := obj.Book(start,end);
 */
